package com.yubest;

import java.util.Arrays;

/**
 * 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
 * <p>
 *  
 * <p>
 * 示例：
 * <p>
 * 输入：nums = [-1,2,1,-4], target = 1
 * 输出：2
 * 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
 *  
 * <p>
 * 提示：
 * <p>
 * 3 <= nums.length <= 10^3
 * -10^3 <= nums[i] <= 10^3
 * -10^4 <= target <= 10^4
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/3sum-closest
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/10/26 15:28
 */
public class P0016 {

    public static void main(String[] args) {
        System.out.println(new Solution16().threeSumClosest(new int[]{-1, 2, 1, -4}, 1));

        System.out.println(new Solution16().threeSumClosest(new int[]{1, 1, -1, -1, 3}, 3));
    }
}

class Solution16 {

    /**
     * 思路：先排序，然后暴力解法，三层循环
     * @param nums
     * @param target
     * @return
     */
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int len = nums.length;
        int r = nums[0] + nums[1] + nums[2];
        int diff = Math.abs(r - target);

        int tempR, tempDiff;
        for (int first = 0; first < len; first++) {
            //过滤重复的计算
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            for (int second = first + 1; second < nums.length; second++) {
                //过滤重复的计算
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                for (int third = second + 1; third < nums.length; third++) {
                    //过滤重复的计算
                    if (third > second + 1 && nums[third] == nums[third - 1]) {
                        continue;
                    }
                    tempR = nums[first] + nums[second] + nums[third];
                    tempDiff = Math.abs(tempR - target);
                    if (tempDiff == 0) {
                        return target;
                    }
                    if (tempDiff < diff) {
                        r = tempR;
                        diff = tempDiff;
                    }
                }
            }
        }
        return r;
    }
}
